//
// Created by 高森森 on 2022/2/17.
//

#ifndef LEETCODE_SOLUTION56_H
#define LEETCODE_SOLUTION56_H

#include <iostream>
using namespace std;
#include<vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

class Solution56 {
public:
    unordered_map<string ,unordered_set<int>>map;
    int scoreOfStudents(string s, vector<int>& answers) {
        unordered_set<int>errRes=getErrRes(s);
        int right=getRight(s);
        auto it=errRes.erase(right);
        int ans=0;
        for(int i=0;i<answers.size();i++){
            int a=answers[i];
            if(a==right)
                ans+=5;
            else if(errRes.count(a))
                ans+=2;
        }
        return ans;
    }
    int getRight(string &s){
        stack<int>stack;
        stack.push(s[0]-'0');
        for(int i=1;i<s.length();i+=2){
            if(s[i]=='+'){
                stack.push(s[i+1]-'0');
            }
            else{
                stack.top()*=(s[i+1]-'0');
            }
        }
        int sum=0;
        while(!stack.empty()){
            sum+=stack.top();
            stack.pop();
        }
        return sum;
    }
    unordered_set<int> getErrRes(const string &s){
        unordered_set<int>errres;
        if(s.length()==1)
            errres.insert(s[0]-'0');
        if(map.count(s)){
            return map[s];
        }
        for(int i=1;i<s.length();i+=2){
            char ch =s[i];
            unordered_set<int>leftSet=getErrRes(s.substr(0,i-0));
            unordered_set<int>rightSet=getErrRes(s.substr(i+1));
            for(int left:leftSet)
                for(int right:rightSet){
                    int val=(ch=='*'?(left*right):left+right);
                    if(val<=1000)
                        errres.insert(val);
                }
        }
        map[s]=errres;
        return errres;
    }
    int scoreOfStudents2(string s, vector<int>& answers) {
        int len = s.length();
        //统计学生答案
        vector<int> count(1001);
        for (int p:answers)
            count[p]++;
        //计算正确结果
        stack<int> stack;
        stack.push(s[0] - '0');
        for (int i = 1; i < s.length(); i += 2) {
            if (s[i] == '+') {
                stack.push(s[i + 1] - '0');
            } else {
                stack.top() *= (s[i + 1] - '0');
            }
        }
        int sum = 0;
        while (!stack.empty()) {
            sum += stack.top();
            stack.pop();
        }
        //计算正确结果的得分
        int ans = 5 * count[sum];
        vector<vector<unordered_set<int>>> dp(len, vector<unordered_set<int>>(len));
        //枚举其他所有的可能结果 dp[i][j]表示字符串s[i,j]的所有可能结果
        for (int j = 0; j < len; j += 2) {
            dp[j][j].insert(s[j] - '0');
        }//相当于dfs的递归出口
        for (int step = 2; step < len; step += 2) {
            //枚举左半部分的开始位置i
            for (int i = 0; i + step < len; i += 2) {
                //枚举左半部分的长度t
                for (int t = 0; t < step; t += 2) {
                    //x是左半部分的所有可能值
                    //y是右半部分的所有可能值
                    for (auto x:dp[i][i + t]) {
                        for (auto y:dp[i + t + 2][i + step]) {
                            //根据左半部分和右半部分的中间连接符来计算后的值
                            int tmp = s[i + t + 1] == '+' ? x + y : x * y;
                            if (tmp <= 1000)
                                dp[i][i + step].insert(tmp);
                        }
                    }
                }
            }
        }
        //统计错误同学得分
        for(int p:dp[0][len-1]){
            if(p!=sum){
                ans+=2*count[p];
            }
        }
        return ans;
    }

};


#endif //LEETCODE_SOLUTION56_H
